import functools
class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        coins = set(coins)
        coin_min = min(coins)

        @functools.cache
        def search(amount):
            if amount == 0:
                return 0
            if amount in coins:
                return 1
            else:
                if amount < coin_min:
                    return - 1
                else:
                    flag = False
                    for item in coins:
                        if item < amount:
                            last_count = search(amount - item)
                            if last_count != -1:
                                if not flag:
                                    flag = True
                                    min_value = last_count + 1
                                else:
                                    min_value = min(min_value, last_count + 1)
                    if flag:
                        return min_value
                    else:
                        return - 1

        return search(amount)


data = Solution()
coins = [1]
amount = 0
print(data.coinChange(coins, amount))